package leetcode.top100;

import leetcode.pre200.Code191_BitOf1;

/**
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 2
 * 输出: [0,1,1]
 * 示例 2:
 * <p>
 * 输入: 5
 * 输出: [0,1,1,2,1,2]
 * <p>
 * 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。
 * <p>
 * 但你可以在线性时间O(n)内用一趟扫描做到吗？
 * 要求算法的空间复杂度为O(n)。
 * <p>
 * 基础见{@link Code191_BitOf1}
 *
 * @date 2020/5/5 20:47
 */
public class Code338_BitCountOf1 {

    /**
     * 方式1：O(n*sizeof(integer))
     */
    public int[] countBits(int num) {
        if (num < 0) return new int[0];
        int[] res = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            res[i] = Integer.bitCount(i);
        }
        return res;
    }

    /**
     * 方式2：O(n)时间。利用奇偶数前后关系。
     * 奇数位数 = 偶数位数 + 1. 因为偶数最后一位必然是0，奇数就是由0变1.
     * <p>
     * 偶数 = 偶数 >> 1  。  偶数/2 再往左移动1位，就是偶数
     */
    public int[] countBits2(int num) {
        if (num < 0) return new int[0];
        int[] res = new int[num + 1];
        res[0] = 0;

        for (int i = 1; i <= num; i++) {
            //奇数
            if ((i & 1) == 1) {
                res[i] += res[i - 1] + 1;
            } else {
                res[i] = res[i >> 1] + 1;
            }
        }
        return res;
    }

    /**
     * 方式3：事实上，不管num是奇数还是偶数
     * 如果num是偶数，如 num = 6 = (110),则num/2 = 3 = (11)同oneBit位。
     * 如果num是奇数，那么num/2是偶数，只是把最后一个1给溢出了。
     * 如num = 7 = (111), num/2 = 3 = (11),溢出了1.
     * 如果num=5=(101),num/2 = 2 = (10),溢出了1。
     * 是奇数则 f(num) = f(num/2) +1
     * 是偶数则 f(num) = f(num/2)
     * 从而f(num) = f(num>>1) + num & 1
     *
     * @return
     */
    private int[] countBits3(int nums) {
        int[] res = new int[nums + 1];
        res[0] = 0;
        for (int i = 1; i <= nums; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }

    /**
     * 方式4：我们知道可以通过 x = (x& x-1)把x的 从右到左的第1个bit为1的位置设置为0
     * 所以DP：f(num) = f( num & num-1) +1
     * @param nums
     * @return
     */

    private static int[] process4(int nums) {
        int[] res = new int[nums + 1];
        res[0] = 0;
        for (int i = 1; i <= nums; i++) {
            // i & (i-1)在i之前肯定被算出来了，根据关系得到i
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }

    private boolean powOf2(int n) {
        return (n & (n - 1)) == 0;
    }

    private boolean powOf2_2(int n) {
        // n& -n  是把n的最右侧的1拿出来
        return (n & -n) == n;
    }

    public static void main(String[] args) {
        Code338_BitCountOf1 main = new Code338_BitCountOf1();
        for (int i = 0; i < 10000; i++) {
            if (main.powOf2(i) != main.powOf2_2(i)) {
                System.out.println("err");
            }
        }
    }
}
